package double_pointer;

import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @Description 18. 四数之和 https://leetcode.cn/problems/4sum/
 * @Author Firenut
 * @Date 2023-02-17 14:19
 */
public class T18_fourSum {
    @Test
    public void test() {
//        fourSum(new int[]{1, 0, -1, 0, -2, 2}, 0);

        // 注意测试用例中 nums[i]的数可能很大，导致累加结果溢出,所以要用long
        fourSum(new int[]{0, 0, 0, 1000000000, 1000000000, 1000000000, 1000000000}, 1000000000);
    }

    // 注意测试用例中 nums[i]的数可能很大，导致累加结果溢出,所以要用long
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> ans = new ArrayList<>();
        int len = nums.length;
        Arrays.sort(nums);
        for (int i = 0; i < nums.length - 3; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }

            // 剪枝
            if ((long)nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) {
                break;
            }
            // if(nums[i]+nums[len-1]+nums[len-2]+nums[len-3]>target){
            //     break;
            // }
//            int temp = nums[i] + nums[len - 1] + nums[len - 2] + nums[len - 3];

            // 剪枝
            if ((long) nums[i] + nums[len - 1] + nums[len - 2] + nums[len - 3] < target) {
                // break;
                continue;
            }

            for (int j = i + 1; j < nums.length - 2; j++) {
                // if(nums[j]==nums[j-1]){
                //     continue;
                // }

                // 剪枝
                if (j > i + 1 && nums[j] == nums[j - 1]) { // ** nums[i]和nums[j]的值相同是没有关系的
                    continue;
                }
                // 剪枝
                if ((long) nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target) {
                    break;
                }
                // 剪枝
                if ((long) nums[i] + nums[j] + nums[len - 1] + nums[len - 2] < target) {
                    // break;
                    continue;
                }
                int left, right;
                left = j + 1;
                right = nums.length - 1;
                while (left < right) {
                    long sum = (long)nums[i] + nums[j] + nums[left] + nums[right];
                    if (sum < target) {
                        while (left < right && nums[left] == nums[++left]) ;
                    } else if (sum > target) {
                        while (left < right && nums[right] == nums[--right]) ;
                    } else {
                        ans.add(new ArrayList<>(Arrays.asList(nums[i], nums[j], nums[left], nums[right])));
                        while (left < right && nums[left] == nums[++left]) ;
                        while (left < right && nums[right] == nums[--right]) ;
                    }
                }
            }
        }
        return ans;
    }
}